package com.zofer.study.num;

/**
 * 题目：实现函数 int sqrt(int x).
 * 计算并返回x的平方根
 */
public class XSqrtByBinarySearch {

    public static void main(String[] args) {
        System.out.println(sqrt(5));
    }

    /**
     * 二分查找
     */
    public static int sqrt (int x) {
        // write code here
        int start = 1;
        int end = x;
        while(start <= end){
            int mid = (end + start)/2;
            //不要写成middle*middle==x，会溢出
            if(mid == x/mid){
                return mid;
            }else{
                if(mid < x/mid){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }
        }
        return end;
    }
}
